1. Field of Invention
The present invention relates to the design of a data network and more particularly to a method for optimizing system performance in a data network through ingress rate monitoring.
2. Description of Related Art
A flow of data entering a network is routed to a designated queue while other flows are simultaneously routed to their designated queues. A queue can build up (i.e., congest) when the egress rate is less than the ingress rate for that queue. This congestion can lead to poor performance for the underlying tasks. Therefore, the efficient management of congestion is an important goal in the design of a data network.
As illustrated in FIG. 6, a representative data network includes data channels C1'-C3', which take as inputs data from the Flows F1'-F9'. The channels pass data to a switch S', which in turn passes the data to Queues Q1'-Q3'.
The data in each of flows F1'.multidot.F9' consists of a sequence of packets (i.e., units of data). The packets corresponding to a given flow (i.e., one of F1'-F9') pass through a designated channel (i.e., one of C1'-C3') and are routed by Switch S' to a designated queue (i.e., one of Q1'-Q3-).
When the network becomes congested, packets can be dropped due to a lack of resources. Dropped packets must then be resent. This places an additional load on the system that can lead to further congestion.
A packet is dropped according to the RED algorithm (Random Early Detection) in the packet's corresponding queue (i.e., one of Q1'-Q3'). As illustrated by the drop probability curve in FIG. 7, the probability of dropping a packet is set to zero for values of the average queue size less than a lower RED threshold value and is set to one for values greater than an upper RED threshold value. For values of the average queue size in between the two thresholds, the drop probability depends linearly on the average queue size. Once the drop probability of a packet is determined, then the packet may or may not be dropped according to a random test; otherwise, the packet is enqueued. Details of the RED Algorithm are given in "Random Early Detection Gateways for Congestion Avoidance"(Sally Floyd and Van Jacobson, 1993 IEEE/ACM Transactions on Networking), incorporated herein by reference.
The dropping of packets effectively signals congestion in a data network to a higher-level protocol such as TCP, and the higher-level protocol then responds by slowing down the rate of the corresponding flow. When there is no congestion (i.e., no dropping of packets), the higher-level protocol naturally increases the overall traffic in the network until congestion occurs. While the use of RED to signal congestion has some advantages, this approach still can lead to limitations in system performance, which can be characterized by measures such as throughput (i.e., the total amount of data transferred) and goodput (i.e., the amount of data transferred completed tasks).
Because the RED algorithm allows the dropping of packets without regard to the characteristics of a flow, packets may be dropped in a flow that is critical for system performance but is not responsible for congestion in the system. Thus, for example, the RED algorithm does not distinguish between a high-bandwidth flow related to a file transfer and a low-bandwidth flow related to a control signal. In a qualitative sense, the overall performance of the system will benefit by increasing drop probabilities for flows that are causing the congestion.
Attempts to modify the RED algorithm have generally focussed on additional inputs other than ingress measurements and performance criteria other than and system performance.
For example, the FRED algorithm (Flow Random Early Drop) modifies the drop probability according to the RED algorithm by incorporating information on buffer use (i.e., queue usage) so that packets of a flow with high buffer use are more likely to be dropped. The FRED algorithm makes this modification by maintaining per-active-flow buffer counts for each flow that currently has packets buffered. Details of the FRED algorithm are discussed in "Dynamics of Random Early Detection" (Dong Lin and Robert Morris, Proceedings of SIGCOMM'97).
The Adaptive RED algorithm employs a drop probability curve according to the RED algorithm, where the curve can be modified according to some system performance goal; however, flow characteristics and measurements are not used. Details of the Adaptive RED algorithm are discussed in "A Self-Configuring RED Gateway" (Feng et al.).
The WRED algorithm (Weighted Random Early Detection) uses the IP precedence of a packet to modify the drop probability without regard to the flow. That is, a different drop probability curve as in FIG. 7 is used for each IP precedence (from 1 to 8). As a result, one cannot expect improved system performance. A variant of the WRED algorithm also employs different drop probability curves at each queue.
Other approaches have focussed on preferences for certain users. That is, a flow owned by a preferred user can have a drop probability curve with lower values as compared with a curve associated with a non-preferred user. As a result, flows belonging to a preferred user may be benefited, but system performance is not likely to be enhanced. For example, the two-bit scheme allocates a higher-priority queue to a preferred user. Similarly the USD scheme allocates higher bandwidth to a preferred user. The RIO scheme includes two drop probability curves, one for flows "in profile" and one for flows "out of profile" with respect to some flow characterization based in part on the user. The "in profile" curve uses a higher value for the lower RED threshold as compared with the "out of profile" curve. As a result, packets may be dropped for flows that are "out of profile" while the congestion in the system is being caused by flows that are "in profile." Preferences based primarily on user identification cannot be expected to enhance system performance. Details of the two-bit scheme, the USD scheme and the RIO scheme are discussed in "A Comparative Study of Schemes for Differentiated Services" (Anindya Basu and Zheng Wang, IETF Website).
Other non-probabilistic approaches to dropping packets have also been developed. Examples include U.S. Pat. No. 4,769,810 and U.S. Pat. No. 4,769,811. However, for some applications these approaches appear to be less successful in signaling congestion in a data network.